
                               MAPS

{ d1 -> r1, ..., dn -> rn }    map enumeration
{}                             empty map
{ x -> e1 : x <- e2 }          map construction
{ x -> e1 : x <- e2 ; b }      map construction with boolean
dom m                          domain of map m
rng m                          range of map m
m dr s                         domain restriction (s is a set)
m ds s                         domain subtraction (s is a set)
inverse m                      inverse of m
m im s                         image of m (s is a set)
m[x]                           application
m[x,r]                         application with default error return
m1 overwr m2                   overwrite
m[d]= r                        map update
first p                        first element of ordered pair
second p                       second element of ordered pair

Maps are enumerated by delimiting their elements with curly brackets
(because formally maps are sets of ordered pairs). The syntax is
given by the following example.

m = {1->2,3->4,5->6};

where the first and second elements of each ordered pair is separated
by the mapping symbol ->.

Maps can be constructed using map construction. In the following
example, len returns the length of a string.

{x->len x:x <- {"abc","defg","hijkl"}};

         returns {"abc"->3,"defg"->4,"hijkl"->5}

The domain (range) of a map is obtained by forming a set composed
of all the first (second) elements of the ordered pairs

dom m;               returns {1,3,5}
rng m;               returns {2,4,6}

A single-valued map must have all its first elements unique. Notice
that, in general, card (rng m) <= card (dom m). The cardinality of
the range would be less, for example if

m = {1->2,3->2,5->6};

In this case, card(dom m) = 3, and card(rng m) = 2 (because of the
duplicate elements in the range).

Given a domain element, we can obtain the corresponding range element
using application (this is like a table lookup).

m[1];                returns 2
m[5];                returns 6

If a domain element is given which does not exist in the map, a false
value will be returned. However, it is possible to supply your own
value to be returned in this situation. This is done by supplying an
additional argument (called the default error return). For example,

m[7];                returns false
m[7,"not found"];    returns "not found"

Given a set of domain elements as a second argument, the image operation
(im) produces a set of the corresponding range elements (again assuming
m={1->2,3->4,5->6})

m im {3,5};        returns {4,6}

Domain restriction (dr) and domain subtraction (ds) produce new maps
from a given map by either allowing only certain domain elements in
the given map to appear in the result map, or taking away certain
domain elements from the given map. The domain elements are given
in a set which is the second argument of these operations.

{1->2,3->2,5->6} dr {3,5};     returns  {3->2,5->6}
{1->2,3->2,5->6} ds {3,5};     returns {1->2}

The inverse operation just interchanges the domain and range elements
of a map.

inverse {1->2,3->2,5->6};      returns {2->1,2->3,6->5}

Note that the result of the above operation is a multi-valued map.

The overwrite operation m1 overwr m2 is defined as follows: Each
mapping in m1 is included in the result, unless its domain element
occurs in the domain of m2. In that case, it is replaced by the
mapping from m2. Every mapping in m2 whose domain element does not
occur in the domain of m1 is included in the result. Example:

{1->2,3->4} overwr {3->5,4->6};    returns {1->2,3->5,4->6}

The map update m[d]=r is an assignment and a special case of
overwrite where the second operand (of overwrite) contains a
single ordered pair. Assuming that m is equal to {1->2,3->4},
m[3]=5; is equivalent to m overwr {3->5} and assigns to m the map
{1->2,3->5}.
